import java.util.*;

public class IDDepthFirstSearch {
	public static List<State> solve(State start, State goal) {
		final int MAX_DEPTH = 35;
		int iterationDepth = 0;
		while (iterationDepth < MAX_DEPTH)  { 
		
		// LIFO collection of nodes that have not been explored.
				Stack<State> frontier = new Stack<>();
				// Collection (with fast search) holding nodes in the current search
				// path or in the frontier.  Each node maps to its parent node.
				Map<State,State> pathAndFrontier = new HashMap<>();
				// If the DFS has backtracked, records the State backtracked from
				// (null otherwise).
				State backtrackFrom = null;
				// The total number of nodes explored.
				int nodesExplored = 0;
				// The total number of nodes that have been in the frontier.
				int nodesInFrontier = 0;
				// The total number of nodes created.
				int nodesCreated = 0;
				
				int depth =0;

				frontier.add(start);
				pathAndFrontier.put(start, null);
				nodesInFrontier++;
				while ((!frontier.isEmpty())) {
					State node = frontier.pop();
					depth++;
					nodesExplored++;
					if (backtrackFrom != null) {
						State nodeParent = pathAndFrontier.get(node);
						do {
							backtrackFrom = pathAndFrontier.remove(backtrackFrom);
							depth--;
						} while (backtrackFrom != nodeParent);
					}
					backtrackFrom = node;
					if(depth < iterationDepth)
					{
						for (State child : node.getNeighbors()) {
							nodesCreated++;
							if (!pathAndFrontier.containsKey(child)) {
								frontier.add(child);
								pathAndFrontier.put(child, node);
								nodesInFrontier++;
								backtrackFrom = null;
								if (child.equals(goal)) {
									return displaySolutionPath(child, pathAndFrontier);
								}
							}
						}
					}
				}
				iterationDepth++;
			}
				System.out.println("No solultion found");
				return null;
			}
	
	public static List<State> displaySolutionPath(State node, Map<State,State> parentMap) {
		LinkedList<State> path = new LinkedList<>();
		while (node != null) {
			path.addFirst(node);
			node = parentMap.get(node);
		}
		return path;
	}
}
		